#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1010;
int n, m;
struct node {
	int ne;
	int w;
};
vector<node> v[N];
int a[N];
ll dis[N];
bool vis[N] = { false };
void dfs()
{
	memset(dis, 0x3f3f3f, sizeof(dis));
	dis[1] = 0;
	for (int i = 0; i < n; i++)
	{
		int u = 0;
		for (int j = 1; j <= n; j++)
		{
			if (!vis[j] && dis[j] < dis[u]) {
				u = j;
			}
		}
		vis[u] = true;
		for (auto& edge : v[u])
		{
			int ne = edge.ne;
			int w = edge.w;
			if (!vis[ne] && dis[u] + w + a[ne] < dis[ne]) {
				dis[ne] = dis[u] + w + a[ne];
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back({ y,z });
		v[y].push_back({ x,z });
	}
	dfs();
	cout << dis[n] - a[n] << endl;
	return 0;
}